#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;
int maxAreaRec(vector<int>& height, int i, int j) 
{
    return i == j ? 0 : 
        (height[i] > height[j] ? max(maxAreaRec(height, i, j-1), height[j] * (j - i)) 
            : max(maxAreaRec(height, i+1, j), height[i] * (j - i)));

}

int maxArea(vector<int>& height) 
{
   // return maxAreaRec(height, 0, height.size()-1);

        int i=0,j=height.size()-1,ans = 0;
        while(j>i)
        {
            ans = max(min(height[i],height[j])*(j-i),ans);
            if(height[i]>height[j]) j--;
            else i++;
        }
       
 //cout <<"i,j:"<<i<<","<<j<<endl;
 return ans;


 // return ret;

}


int main(int argc,char *argv[])
{


  vector<int> height1={2,3,1,2,1,1};

  vector<int> height2;
  for(int i=15000;i>0;--i)
    height2.push_back(i);

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);
  cout<<maxArea(height1 )<<endl;
  int time2 = gettimeofday(&tv2,&tz);
  cout << "height 1 time consuming:" << tv2.tv_usec - tv1.tv_usec <<"us"<< endl;

  gettimeofday(&tv1,&tz);
  cout<<maxArea(height2 )<<endl;
  gettimeofday(&tv2,&tz);
  cout << "height2 time consuming:" << tv2.tv_usec - tv1.tv_usec <<"us"<< endl;




  return 0;
}
